<?xml version="1.0" encoding="utf-8" ?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<meta name="generator" content="Docutils 0.4: http://docutils.sourceforge.net/" />
<title>Packet Link Layer</title>
<meta name="author" content="David Moss, Philip Levis" />
<style type="text/css">

/*
:Author: David Goodger
:Contact: goodger@users.sourceforge.net
:date: $Date: 2009/02/03 23:07:32 $
:version: $Revision: 1.2 $
:copyright: This stylesheet has been placed in the public domain.

Default cascading style sheet for the HTML output of Docutils.
*/
body {
  font-family: Times;
  font-size: 16px;
}

.first {
  margin-top: 0 ! important }

.last {
  margin-bottom: 0 ! important }

.hidden {
  display: none }

a.toc-backref {
  text-decoration: none ;
  color: black }

blockquote.epigraph {
  margin: 2em 5em ; }

dd {
  margin-bottom: 0.5em }

div.abstract {
  margin: 2em 5em }

div.abstract p.topic-title {
  font-weight: bold ;
  text-align: center }

div.attention, div.caution, div.danger, div.error, div.hint,
div.important, div.note, div.tip, div.warning, div.admonition {
  margin: 2em ;
  border: medium outset ;
  padding: 1em }

div.attention p.admonition-title, div.caution p.admonition-title,
div.danger p.admonition-title, div.error p.admonition-title,
div.warning p.admonition-title {
  color: red ;
  font-weight: bold ;
  font-family: sans-serif }

div.hint p.admonition-title, div.important p.admonition-title,
div.note p.admonition-title, div.tip p.admonition-title,
div.admonition p.admonition-title {
  font-weight: bold ;
  font-family: sans-serif }

div.dedication {
  margin: 2em 5em ;
  text-align: center ;
  font-style: italic }

div.dedication p.topic-title {
  font-weight: bold ;
  font-style: normal }

div.figure {
  margin-left: 2em }

div.footer, div.header {
  font-size: smaller }

div.line-block {
  display: block ;
  margin-top: 1em ;
  margin-bottom: 1em }

div.line-block div.line-block {
  margin-top: 0 ;
  margin-bottom: 0 ;
  margin-left: 1.5em }

div.sidebar {
  margin-left: 1em ;
  border: medium outset ;
  padding: 0em 1em ;
  background-color: #ffffee ;
  width: 40% ;
  float: right ;
  clear: right }

div.sidebar p.rubric {
  font-family: sans-serif ;
  font-size: medium }

div.system-messages {
  margin: 5em }

div.system-messages h1 {
  color: red }

div.system-message {
  border: medium outset ;
  padding: 1em }

div.system-message p.system-message-title {
  color: red ;
  font-weight: bold }

div.topic {
  margin: 2em }

h1 {
  font-family: Arial, sans-serif;
  font-size: 20px;
}

h1.title {
 text-align: center;
 font-size: 32px;
}

h2 {
 font-size: 16px;
 font-family: Arial, sans-serif;
}

h2.subtitle {
  text-align: center }

h3 {
 font-size: 12px;
 font-family: Arial, sans-serif;
}

hr {
  width: 75% }

ol.simple, ul.simple {
  margin-bottom: 1em }

ol.arabic {
  list-style: decimal }

ol.loweralpha {
  list-style: lower-alpha }

ol.upperalpha {
  list-style: upper-alpha }

ol.lowerroman {
  list-style: lower-roman }

ol.upperroman {
  list-style: upper-roman }

p.attribution {
  text-align: right ;
  margin-left: 50% }

p.caption {
  font-style: italic }

p.credits {
  font-style: italic ;
  font-size: smaller }

p.label {
  white-space: nowrap }

p.rubric {
  font-weight: bold ;
  font-size: larger ;
  color: maroon ;
  text-align: center }

p.sidebar-title {
  font-family: sans-serif ;
  font-weight: bold ;
  font-size: larger }

p.sidebar-subtitle {
  font-family: sans-serif ;
  font-weight: bold }

p.topic-title {
  font-weight: bold }

pre.address {
  margin-bottom: 0 ;
  margin-top: 0 ;
  font-family: serif ;
  font-size: 100% }

pre.line-block {
  font-family: serif ;
  font-size: 100% }

pre.literal-block, pre.doctest-block {
  margin-left: 2em ;
  margin-right: 2em ;
  background-color: #eeeeee;
  border-color: #000000;
  border-width: thin; 
  font-size: 14px
}

span.classifier {
  font-family: sans-serif ;
  font-style: oblique }

span.classifier-delimiter {
  font-family: sans-serif ;
  font-weight: bold }

span.interpreted {
  font-family: sans-serif }

span.option {
  white-space: nowrap }

span.option-argument {
  font-style: italic }

span.pre {
  white-space: pre }

span.problematic {
  color: red }

table {
  margin-top: 0.5em ;
  margin-bottom: 0.5em }

table.citation {
  border-left: solid thin gray ;
  padding-left: 0.5ex }

table.docinfo {
  margin: 2em 4em;
}

table.footnote {
  border-left: solid thin black ;
  padding-left: 0.5ex }

td, th {
  padding-left: 0.5em ;
  padding-right: 0.5em ;
  vertical-align: top }

th.docinfo-name, th.field-name {
  font-weight: bold ;
  text-align: left ;
  white-space: nowrap;
  }

h1 tt, h2 tt, h3 tt, h4 tt, h5 tt, h6 tt {
  font-size: 100% }

tt {}

ul.auto-toc {
  list-style-type: none }

</style>
</head>
<body>
<div class="document" id="packet-link-layer">
<h1 class="title">Packet Link Layer</h1>
<table class="docinfo" frame="void" rules="none">
<col class="docinfo-name" />
<col class="docinfo-content" />
<tbody valign="top">
<tr class="field"><th class="docinfo-name">TEP:</th><td class="field-body">127</td>
</tr>
<tr class="field"><th class="docinfo-name">Group:</th><td class="field-body">Core Working Group</td>
</tr>
<tr class="field"><th class="docinfo-name">Type:</th><td class="field-body">Documentary</td>
</tr>
<tr><th class="docinfo-name">Status:</th>
<td>Draft</td></tr>
<tr class="field"><th class="docinfo-name">TinyOS-Version:</th><td class="field-body">2.x</td>
</tr>
<tr><th class="docinfo-name">Author:</th>
<td>David Moss, Philip Levis</td></tr>
</tbody>
</table>
<div class="note">
<p class="first admonition-title">Note</p>
<p class="last">This memo documents a part of TinyOS for the TinyOS Community, and
requests discussion and suggestions for improvements.  Distribution
of this memo is unlimited. This memo is in full compliance with
TEP 1.</p>
</div>
<div class="section">
<h1><a id="abstract" name="abstract">Abstract</a></h1>
<p>This TEP describes the behavior and interfaces of the TinyOS 2.x
Packet Link Layer.  The Packet Link Layer is an optional radio stack
layer responsible for the reliable delivery of a packet from node to
node.  Packet Link provides error correction functionality found in
Layer 2 of the OSI model <a class="footnote-reference" href="#id2" id="id1" name="id1">[1]</a>.</p>
</div>
<div class="section">
<h1><a id="introduction" name="introduction">1. Introduction</a></h1>
<p>In wireless networks, packets are regularly dropped between point to point
communications due to interference or RF range.  Correcting these dropped
packets requires the transmitter to first recognize that the packet was
not acknowledged, and then retransmit that packet.</p>
<p>Retransmitting the packet adds its own set of issues.  Specifically, the
receiver will receive duplicate packets due to its own dropped acknowledgements.
Logic is therefore required to allow receiver to recognize and dump duplicate
packets, but only after the acknowledgement has been sent back to the
transmitter.</p>
<p>With these two pieces of functionality: the ability for a transmitter to
keep retrying until it gets an acknowledgement and the ability
for a receiver to accept only a single copy of the packet, a Packet Link Layer
can be formed to reliably deliver a single packet from point to point.</p>
</div>
<div class="section">
<h1><a id="design-considerations" name="design-considerations">2. Design Considerations</a></h1>
<div class="section">
<h2><a id="time-spent-retrying-a-delivery" name="time-spent-retrying-a-delivery">2.1 Time spent retrying a delivery</a></h2>
<p>Some networks have different timing characteristics than others.
Consider a person carrying a wireless device while walking in and out
of RF range of another node.  In this case, the device may want to
retry the transmission a few times over the course of a few seconds before
declaring the delivery unsuccessful.  A robust Packet Link Layer should
allow the developer to specify the amount of time spent retrying as well
as the number of retries to send.</p>
</div>
<div class="section">
<h2><a id="setting-the-packet-sequence-number" name="setting-the-packet-sequence-number">2.2 Setting the packet sequence number</a></h2>
<p>To detect duplicate packets, a sequence number byte can be used
within the packet to verify against previously received
packets.  If the source address and sequence number of a newly received
packet matches that of a previously received packet, then the newly received
packet is a duplicate and may be dumped.  To prevent the packet sequence
number byte from changing on each retransmission, the byte should be set
at or above the Packet Link Layer and never changed below.</p>
</div>
<div class="section">
<h2><a id="false-acknowledgements" name="false-acknowledgements">2.3 False Acknowledgements</a></h2>
<p>The low levels of a radio stack or the radio chip itself are typically
responsible for generating packet acknowledgements.  It has been
observed in some platforms that the radio chip will generate false
auto-acknowledgements. This occurs when the radio receives the packet and
sends an acknowledgement but the microcontroller never gets the message
due to some error.  In this case, the transmitter would believe the
packet got to the destination successfully but the receiver would have
no knowledge that a packet was received. Software initiated
acknowledgements prevent this issue by removing the possibility of
false acknowledgements.</p>
</div>
</div>
<div class="section">
<h1><a id="interface" name="interface">3. Interface</a></h1>
<div class="section">
<h2><a id="packetlink-interface" name="packetlink-interface">3.1 PacketLink Interface</a></h2>
<p>The TEP proposes this PacketLink interface::</p>
<pre class="literal-block">
interface PacketLink {
  command void setRetries(message_t *msg, uint16_t maxRetries);
  command void setRetryDelay(message_t *msg, uint16_t retryDelay);
  command uint16_t getRetries(message_t *msg);
  command uint16_t getRetryDelay(message_t *msg);
  command bool wasDelivered(message_t *msg);
}
</pre>
<p>PacketLinks interface functions:</p>
<blockquote>
<tt class="docutils literal"><span class="pre">setRetries(message_t</span> <span class="pre">*msg,</span> <span class="pre">uint16_t</span> <span class="pre">maxRetries)</span></tt></blockquote>
<ul>
<li><p class="first">Sets the maximum number of times to retry the transmission of the message</p>
<p><tt class="docutils literal"><span class="pre">setRetryDelay(message_t</span> <span class="pre">*msg,</span> <span class="pre">uint16_t</span> <span class="pre">retryDelay)</span></tt></p>
</li>
<li><p class="first">Set the delay, in milliseconds, between each retransmission</p>
<p><tt class="docutils literal"><span class="pre">getRetries(message_t</span> <span class="pre">*msg)</span></tt></p>
</li>
<li><p class="first">Returns the maximum number of retries configured for the given message</p>
<p><tt class="docutils literal"><span class="pre">getRetryDelay(message_t</span> <span class="pre">*msg)</span></tt></p>
</li>
<li><p class="first">Returns the delay, in milliseconds, between each retransmission for the given
message</p>
<p><tt class="docutils literal"><span class="pre">wasDelivered(message_t</span> <span class="pre">*msg)</span></tt></p>
</li>
<li><p class="first">This command may be called after the sendDone() event is signaled. It is the
equivalent of <tt class="docutils literal"><span class="pre">PacketAcknowledgements.wasAcked(message_t</span> <span class="pre">*msg)</span></tt>, so is only
a helper function to make the PacketLink interface easier to use.</p>
</li>
</ul>
</div>
<div class="section">
<h2><a id="expected-behavior" name="expected-behavior">3.2 Expected Behavior</a></h2>
<p>The PacketLink interface is accessed by the application layer before
the packet is passed to the radio stack for transmission.  The application
layer will call setRetries(...) and setRetryDelay(...), passing in the
message it is about to send.</p>
<p>The interface MUST configure metadata for the packet to specify the maximum
number of retries and the amount of delay between each retry. When the
send process reaches the Packet Link Layer, it MUST automatically check the
packet's metadata and retry sending the packet as previously configured.</p>
<p>For example, to configure a packet to be retried a maximum of 50 times
over the next 5 seconds, the developer would execute the following commands
before sending the packet::</p>
<pre class="literal-block">
call PacketLink.setRetries(msg, 50);
call PacketLink.setRetryDelay(msg, 100);
</pre>
<p>By placing a 100 ms delay between each retry and allowing up to 50 retries
maximum, the maximum amount of time the message will be transmitted is
(50 * 100) ms, or 5000 ms.</p>
<p>When transmitting a packet configured for reliable delivery to the
broadcast address, the Packet Link Layer SHOULD allow the packet to be
retried.  This will let the transmitter know that at least one node
received the message.</p>
</div>
</div>
<div class="section">
<h1><a id="author-s-address" name="author-s-address">4. Author's Address</a></h1>
<div class="line-block">
<div class="line">David Moss</div>
<div class="line">Rincon Research Corporation</div>
<div class="line">101 N. Wilmot, Suite 101</div>
<div class="line">Tucson, AZ  85750</div>
<div class="line"><br /></div>
<div class="line">phone - +1 520 519 3138</div>
<div class="line">email ? <a class="reference" href="mailto:dmm&#64;rincon.com">dmm&#64;rincon.com</a></div>
<div class="line"><br /></div>
<div class="line"><br /></div>
<div class="line">Philip Levis</div>
<div class="line">358 Gates Hall</div>
<div class="line">Stanford University</div>
<div class="line">Stanford, CA 94305-9030</div>
<div class="line"><br /></div>
<div class="line">phone - +1 650 725 9046</div>
<div class="line">email - <a class="reference" href="mailto:pal&#64;cs.stanford.edu">pal&#64;cs.stanford.edu</a></div>
<div class="line"><br /></div>
</div>
</div>
<div class="section">
<h1><a id="citations" name="citations">5. Citations</a></h1>
<table class="docutils footnote" frame="void" id="id2" rules="none">
<colgroup><col class="label" /><col /></colgroup>
<tbody valign="top">
<tr><td class="label"><a class="fn-backref" href="#id1" name="id2">[1]</a></td><td>&quot;OSI model&quot; <a class="reference" href="http://en.wikipedia.org/wiki/OSI_model">http://en.wikipedia.org/wiki/OSI_model</a></td></tr>
</tbody>
</table>
</div>
</div>
</body>
</html>
